CPU 스케줄링

개요

CPU 스케줄러는 여러 프로세스의 상황을 고려해 CPU와 시스템 자원을 어떻게 배분할지 결정한다. 즉, 프로세스의 모든 상태 변화를 조정하는 것이다.

종류

CPU 스케줄러는 프로세스 관리의 범주를 나누어 스케줄링한다. 규모에 따라 장기 스케줄러, 중기 스케줄러, 단기 스케줄러로 구분된다.

장기 스케줄러: 시스템 내 전체 작업 수를 조절한다.
- 현대 OS에선 사용 빈도가 낮다.
중기 스케줄러: 시스템 내 부하를 조절하기 위해 과부하 전 프로세스를 보류 상태로 보내거나 보류 상태의 프로세스를 활성화한다.
단기 스케줄러: 어떤 프로세스에 CPU를 할당할 것인지 결정한다.
- CPU 스케줄링에서 가장 중요한 역할 담당

목적

공평성: 모든 프로세스가 자원을 공평하게 배정받아야 한다.
효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링 해야 한다.
안정성: 우선순위를 사용해 중요 프로세스가 먼저 작동되도록 함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 해야 한다.
반응 시간 보장: 시스템이 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
무한 연기 방지: 특정 프로세스의 작업이 무한하게 연기되어선 안 된다.

스케줄링 시 고려 사항

스케줄러가 어떤 프로세스에 우선적으로 CPU를 할당할지 결정할 때 고려해야할 사항이 있다.

선점형 스케줄러와 비선점형 스케줄러

구분	선점형 스케줄러	비선점형 스케줄러
작업 방식	실행 중인 프로세스가 끝나기 전에, 우선순위가 높은 프로세스가 CPU를 점유할 수 있다	실행 중인 프로세스가 끝날 때까지 CPU 점유를 유지하며, 다른 프로세스는 대기한다.
장점	- 응답 시간이 짧아 사용자 작업의 응답성이 향상된다 - 긴 작업을 대기시키고 짧은 작업을 우선 처리 가능하다 - 동적 우선순위 변경이 가능하다	- 구현이 단순하고, 컨텍스트 스위칭 비용이 적다 - CPU가 특정 작업에 집중할 수 있어 처리량(Throughput)이 증가한다
단점	- 잦은 컨텍스트 스위칭으로 CPU 오버헤드 발생한다	- 프로세스 간 공정성이 떨어질 수 있다 - 긴 작업이 완료되기 전까지 다른 작업이 계속 대기(컨보이 효과)할 가능성이 있다
사용 사례	- 시분할 방식 스케줄링에 사용된다	- 일괄 작업 방식 스케줄링에 사용된다

프로세스 우선순위

프로세스에 우선순위가 있다는 것은 중요도가 다르다는 것이다. 프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉘며, 커널 프로세스가 일반 프로세스보다 우선순위가 높다.

일반 프로세스도 중요도가 각각 다르기 때문에 우선순위가 다르다. 이 우선순위는 사용자가 조절이 가능하다. 하지만 특정 프로세스에 우선순위를 너무 높이면, 다른 프로세스 처리에 영향이 가기 때문에 유닉스에선 관리자에게만 해당 권한을 부여한다.

CPU 집중 프로세스와 I/O 집중 프로세스

프로세스는 CPU를 사용해 작업하는 실행 상태 또는 I/O를 요청해 완료되기까지 기다리는 대기 상태에 있다. 이때 CPU를 할당받아 실행하는 작업을 CPU burst, I/O 작업을 I/O burst라고 한다. 프로세스는 위 작업 형태에 따라 CPU 집중 프로세스와 I/O 집중 프로세스로 나눌 수 있다. CPU 집중 프로세스는 CPU burst가 많고, I/O 집중 프로세스는 I/O burst가 많다.

두 프로세스가 있다고 할 때 어떤 프로세스의 우선순위를 높이는 것이 효율적일까? 위에서 볼 수 있듯 I/O 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. I/O 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우를 사이클 훔치기 라고 한다.

다중 큐

준비 상태의 다중 큐

프로세스는 저마다 중요도가 다르며 중요도는 PCB에 표시된다. 스케줄러가 모든 프로세스의 PCB를 뒤져 우선순위가 높은 프로세스를 찾으려면 상당히 번거로울 것이다.

따라서 우선순위에 따라 여러 개의 큐를 만들어 프로세스를 분리한다. 이를 간단히 도식화하면 다음과 같다.

프로세스의 우선순위를 배정하는 방식은 고정 우선순위 방식과 변동 우선순위 방식이 있다.

고정 우선순위 방식: 프로세스에 부여된 우선순위가 프로세스가 종료될 때까지 바뀌지 않는다.
- 장점: 구현이 쉽다.
- 단점: 시스템 변화에 대응하기 어려워 효율이 떨어진다.
변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 작업 중간에 변한다.
- 장점: 시스템 효율을 높인다.
- 단점: 구현이 어렵다.

대기 상태의 다중 큐

대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모인 곳이다. 여기선 같은 I/O를 요구한 프로세스들끼리 모아놓는다. I/O 작업이 끝나고 인터럽트가 도착하면, 준비 상태가 된다.

준비 상태의 다장 큐는 한 번에 하나의 프로세스를 꺼내 CPU에게 할당하지만, 대기큐는 여러 개의 PCB를 동시에 꺼내 준비 상태로 옮긴다. 이렇게 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조를 사용한다.

스케줄링 알고리즘

스케줄링 알고리즘의 선택 기준

어떤 스케줄링 알고리즘이 효율적인지 파악하려면 그 기준이 있어야 한다.

CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간
처리량: 단위 시간당 작업을 마친 프로세스의 수
대기 시간: 작업을 요청한 프로세스가 대기하는 시간
응답 시간: 프로세스 시작 후 첫 번째 출력 또는 응답이 나올 때까지 걸리는 시간
반환 시간: 대기 시간 + 실행 시간

비선점형 알고리즘

프로세스가 CPU를 할당받으면 작업이 끝날 때까지 CPU를 놓지 않는다. 이 경우 효율이 떨어져 지금은 거의 사용되지 않는다.

FCFS (First Come, First Served):
- 도착 순서대로 프로세스를 처리
- 장점: 구현이 간단
- 단점: 앞의 긴 작업으로 인해 뒤의 작업이 지연되는 컨보이 효과 발생
SJF (Shortest Job First):
- 실행 시간이 가장 짧은 프로세스를 우선 처리
- 장점: 평균 대기 시간 최소화
- 단점: 우선순위에 밀려 작업이 계속 연기되는 기아 상태 발생 가능

선점형 알고리즘

시분할 시스템을 고려하여 만들어진 알고리즘으로, 어떤 프로세스가 CPU를 할당받아 실행 중이라도 운영체제가 CPU를 빼앗을 수 있다.

Round Robin (RR):
- 모든 프로세스에 동일한 타임 슬라이스를 할당 -> 우선순위가 적용되지 않음
- 장점: 공정성 보장, 짧은 응답 시간
- 단점: 타임 슬라이스가 적절하지 않으면 성능 저하
SRTF (Shortest Remaining Time First):
- SJF 스케줄링과 RR 스케줄링을 혼합한 방식
- 실행 중인 작업보다 남은 실행 시간이 짧은 작업이 도착하면 CPU를 빼앗김
- 장점: 평균 대기 시간 최소화
- 단점: 작업의 실행 시간을 예측하기 어려움
Priority Scheduling (선점형):
- 높은 우선순위의 작업이 도착하면 실행 중인 작업을 중단
- 장점: 중요한 작업을 빠르게 처리
- 단점: 기아 상태 발생 가능

프로세스의 우선순위는 시스템의 효율성이 아닌 프로세스의 중요도를 기준으로 결정된다.

다단계 큐 스케줄링

다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 각각의 큐는 RR방식으로 운영되며, 상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

장점

단순성:
- 큐를 분리하여 처리하므로 구조가 명확하다.

단점

유연성 부족:
- 큐 간 이동이 불가능하므로, 동적으로 프로세스 우선순위를 변경하기 어렵다.
기아 상태(Starvation):
- 우선순위가 낮은 큐에 있는 프로세스가 오랫동안 실행되지 않을 수 있다.

다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다. 이 방식에서 프로세스는 CPU를 사용한 후 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다. 때문에 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화할 수 있다.

물론 프로세스의 우선순위가 낮아진다고 해도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.

또한 이 방식에서는 우선순위에 따라 타임 슬라이스의 크기가 다르다. 프로세스의 우선순위가 낮아질 수록 타임 슬라이스의 크기가 커진다. 따라서 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 한다.

장점

유연성:
- 프로세스 특성에 따라 큐 간 이동이 가능하다
기아 상태 방지:
- 우선순위가 낮은 프로세스도 시간이 지나면 실행될 기회를 얻는다
성능 최적화:
- 짧은 작업은 빠르게 처리하고, 긴 작업은 낮은 우선순위 큐로 이동한다

단점

복잡성 증가:
- 큐 이동 조건과 알고리즘 설계가 복잡하다
컨텍스트 스위칭 비용 증가:
- 프로세스가 큐를 이동할 때 잦은 컨텍스트 스위칭 발생한다